﻿#include<iostream>
#include<string>
using namespace std;
template<class T>
struct Stack
{
	T* _stack;
	int _top;
	int _capacity;
	// 值得注意的是当top初始化为0时，为了表示为空栈，让数据的个数就是top的值，以示区分
	Stack(int capacity = 0) : _stack(nullptr), _top(0), _capacity(capacity)
	{
		if (_capacity)
		{
			_stack = new T[_capacity];
		}
	}
	~Stack()
	{
		if (_stack)
		{
			while (_top != 0)
			{
				cout << _stack[--_top] << endl;
			}
			delete[] _stack;
		}
		_stack = nullptr;
	}
	void Push(T data)
	{
		// 进来先判断栈容量，为0就设置初始值，非0就扩2倍
		if (_capacity == _top)
		{
			int new_capacity = _capacity == 0 ? 4 : _capacity * 2;
			T* tmp = new T[new_capacity];
			// 有数据就先挪动数据
			for (int i = 0; i < _capacity; i++)
			{
				tmp[i] = _stack[i];
			}
			// 判断_stack是否为空，非空就释放掉权限
			if (_stack)
			{
				delete[] _stack;
			}
			// 将tmp指向的栈交给_stack
			_capacity = new_capacity;
			_stack = tmp;
		}
		// 数据进栈（由于_top是从0开始的，所以是先使用，再自增）
		_stack[_top++] = data;
	}

	// 数据出栈
	void Pop()
	{
		// 注意 考虑_top自减后的结果，当_top为0时才能说栈已空，栈顶的元素的序号_top-1
		if (_top > 0)
			_top--;
		// else
		// {
		//     cout << "Stack is empty!" << endl;
		// }
	}
	T Top()
	{
		if (_top > 0)
		{
			return _stack[_top-- - 1];
		}
		// cout << "No Data!" << endl;
		return 0;
	}
	size_t size()
	{
		return _top;
	}
	bool empty()
	{
		return _top == 0;
	}
};
class Solution
{
public:
	bool isValid(string s)
	{
		Stack<char> st(s.size());
		for (auto e : s)
		{
			if (e == '(' || e == '{' || e == '[')
			{
				st.Push(e);
			}
			else
			{
				char tmp = st.Top();
				if ((tmp == '(' && e == ')') || (tmp == '{' && e == '}') || (tmp == '[' && e == ']'))
					continue;
				else
				{
					return false;
				}
			}
		}
		if (!st.empty())
			return false;
		return true;
	}
};
int main()
{
	cout << Solution().isValid("[]") << endl;
	return 0;
}
